The present invention relates to the field of digital signal processing. Specifically, the present invention relates to a method for efficiently calculating powers of integers using an optimized combination of table lookup and linear approximation which itself uses table lookup.
Many computer applications require the calculation of raising an integer to the power of a real number. In a desktop personal computer, the calculation may be performed by using a floating point processor. Furthermore, a math library may commonly be used to assist the process. However, a fixed point processor may be more suitable for many consumer electronic devices. Among other reasons for this choice, fixed point processors are frequently less expensive than floating point processors. One task that such consumer devices may perform is digital signal processing, which may require the calculation of raising an integer to the power of a real number. However, when performing power calculation with a fixed-point processor, conventional techniques may present undesirable consequences.
One conventional method for performing power calculation with a fixed-point processor is table look-up. However, some applications, such as performing calculation during an inverse quantization step of decoding an MPEG bitstream require a very large table. For example a table with over 8,000 entries may be required. Unfortunately, memory may be limited in many devices in which such decoding is done, for example consumer electronic-devices. Thus, building large tables in undesirable.
Another conventional method for performing power calculation is approximation. However, approximation introduces larger errors and uses more CPU cycles, which is critical to systems with limited CPU and memory resources, such as consumer electronic devices.
Therefore, when using either of these conventional methods, the software engineer chooses between getting a reasonably accurate answer but using a considerable amount of memory or using less memory but consuming more CPU cycles and also, introducing larger errors.
Therefore, it would be advantageous to provide a method for calculating the power of an integer raised to constant real number, which is suitable for use in fixed point processors. A further need exists for such a method which uses limited memory efficiently. A still further need exist for such a method which is computationally efficient. An even further need exists for such a method which, over the most commonly calculated values, does not introduce large errors. A still further need exists for such a method which is suitable for digital signal processing.
The present invention provides a method for efficiently calculating powers of integers using an optimized combination of table lookup and linear approximation which itself uses table lookup. Embodiments of the present invention are well-suited to being used in fixed point processors. Embodiments of the present invention use limited memory efficiently. Embodiments provide for a method which is computationally efficient. Embodiments provide for such a method which, over the most commonly calculated values, does not introduce large errors. Embodiments are suitable for digital signal processing. The present invention provides these advantages and others not specifically mentioned above but described in the sections to follow.
A method for calculating the power of an integer raised to a constant real number is disclosed. For example, in one embodiment, the method may be used to process digital signals, which are encoded in such a fashion as to require such processing. An embodiment of the present invention first receives a segment of a bitstream. Next, the process determines whether an integer value of the segment is within a look-up table. The look-up table contains a plurality of integers and a corresponding plurality of the integers raised to the power of a real number. If the integer value is within the look-up table, the process indexes the look-up table with the integer value to determine substantially the value of the integer raised to the real power. If, however, the integer value is not within the look-up table, the process indexes the table with a plurality of integers which are within the table to approximate the value of the segment from the bitstream raised to the real power. The process repeats these steps for each segment in the signal bitstream.
Another embodiment performs, in addition to the above steps, the step of determining an integer which is larger than the segment divided by the largest integer in the table. This provides a first integer that is used to index the lookup table in the approximation process. Additionally, the process divides the integer value of the segment by the first integer. This provides a second integer that is used to index the lookup table in the approximation process. After indexing the table with the integers, the process combines the results according to a formula. This provides an approximation of the value of the segment raised to the power of the real number. The process may then output the processed signal.
In one embodiment, the input signal is substantially compliant with a Motion Pictures Expert Group (MPEG) format, for example, MPEG audio layer III. In another embodiment, the input signal comprises a plurality of quantized samples.
Another embodiment provides for a computer readable medium containing a computer program that, when executed by a processor, implements a method of processing an encoded information signal-using a combination of straight table lookup and approximation that uses the same table. The encoded information bitstream may contain quantized samples and the method may produce de-quantized samples. In one embodiment, the processor is a fixed point processor.
In yet another embodiment, one of the plurality of integers which is used for approximation is determined before the segment in the bitstream to be processed is accessed. For example, a software engineer determines this integer to be used in approximation based upon the largest expected value of the segment.